package 困难.贪心思想;

import java.util.*;

/**
 * 这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，
 * 其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上
 * durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
 * <p>
 * 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
 * <p>
 * 返回你最多可以修读的课程数目。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/course-schedule-iii
 */
public class 课程表III_630 {

    public static void main(String[] args) {

        int[][] courses = {{100, 200}, {200, 1300}, {1000, 1250}, {2000, 3200}};
        int[][] courses2 = {{7, 17}, {3, 12}, {10, 20}, {9, 10}, {5, 20}, {10, 19}, {4, 18}};
        int[][] courses3 = {{7, 16}, {2, 3}, {3, 12}, {3, 14}, {10, 19}, {10, 16}, {6, 8}, {6, 11}, {3, 13}, {6, 16}};

        System.out.println(efficientCheduleCourse(courses3));

    }

    /**
     * 贪心思想
     * 先学习过期天数较小的课程总是最优的，
     * 如果当前课程不能学习，且当前课程的学习天数比之前学习的课程最大天数小，
     * 那么当前课程和以前的课程进行替换
     *
     * @param courses
     * @return
     */
    public static int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (course1, course2) -> course1[1] - course2[1]);

        int count = 0;  //修读课程门数
        int totalStudyDay = 0;  //已经学习的天数
        List<Integer> preStudyDays = new ArrayList<>();
        for (int[] curCourse : courses) {
            if (curCourse[0] <= curCourse[1]) {  //学习天数小于过期天数
                if (totalStudyDay + curCourse[0] <= curCourse[1]) {  //当前课程可以修读
                    preStudyDays.add(curCourse[0]);
                    totalStudyDay += curCourse[0];
                    count++;
                } else {
                    int maxStudyDay = 0;
                    int maxStudyDayIndex = 0;
                    for (int i = 0; i < preStudyDays.size(); i++) {
                        if (preStudyDays.get(i) > maxStudyDay) {
                            maxStudyDay = preStudyDays.get(i);
                            maxStudyDayIndex = i;
                        }
                    }

                    if (curCourse[0] < maxStudyDay) {
                        //当前课程的学习天数小于前面修读课程学习天数的最大值，那么贪心的选择当前课程，而放弃前面学习天数较多的课程
                        preStudyDays.remove(maxStudyDayIndex);
                        preStudyDays.add(curCourse[0]);
                        totalStudyDay = totalStudyDay - maxStudyDay + curCourse[0];
                    }
                }
            }
        }
        return count;
    }

    /**
     * 贪心思想+优先队列
     * 可以使用优先队列，取出当前课程前学习天数最多的课程
     *
     * @param courses
     * @return
     */
    public static int efficientCheduleCourse(int[][] courses) {
        Arrays.sort(courses, (course1, course2) -> course1[1] - course2[1]);  //根据过期时间升序排序
        int totalStudyDay = 0;  //已经学习的天数
        Queue<Integer> priorityQueue = new PriorityQueue<>(courses.length, (o1, o2) -> o2 - o1);  //优先队列
        for (int[] curCourse : courses) {
            int curStudyDay = curCourse[0], curExpireDay = curCourse[1];
            if (curStudyDay <= curExpireDay) {  //学习天数小于过期天数
                if (totalStudyDay + curStudyDay <= curExpireDay) {  //当前课程可以修读
                    priorityQueue.offer(curStudyDay);
                    totalStudyDay += curStudyDay;
                } else if (curStudyDay < priorityQueue.peek()) {
                    //当前课程的学习天数小于前面修读课程学习天数的最大值，那么贪心的选择当前课程，而放弃前面学习天数较多的课程
                    totalStudyDay = totalStudyDay - priorityQueue.poll() + curStudyDay;
                    priorityQueue.offer(curStudyDay);
                }
            }
        }
        return priorityQueue.size();
    }

}
